COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{F3⊂C<Nα POLYHEDRON INTERSECTION.λ30P50I425,0JCFA} SECTION 5.
C00006 00003	⊂5.1	Intersection Geometry.⊃
C00010 00004	⊂5.2	Intersection Topology.⊃
C00015 00005	⊂5.3	Special Cases.⊃
C00018 00006	⊂5.4	Face Convexity Coercion.⊃
C00020 00007	⊂5.5	Body Cutting.⊃
C00021 00008	⊂5.6	Performance and Related Work.⊃
C00022 ENDMK
C⊗;
{F3;⊂C;<N;α POLYHEDRON INTERSECTION.;λ30;P50;I425,0;JCFA} SECTION 5.
{JCFD} POLYHEDRON INTERSECTION.
{λ10;W250;JAFA}
	5.0	Introduction to Polyhedron Intersection.
	5.1	Intersection Geometry.
	5.2	Intersection Topology.
	5.4	Special Cases of Intersection.
	5.5	Face Convexity.
	5.6	Body Cutting.
	5.7	Performance and Related Work.
{λ30;W0;I950,0;JUFA}
⊂5.0	Introduction to Polyhedron Intersection.⊃

	The  intersection, union  and  set  differences of  two  solid
polyhedra can be computed by combining a body interection procedure
called BIN with the EVERT primitive, as figure 5.1 illustrates.   The
body intersection procedure is important for three reasons: first, it
is  a general and conceptually elegant construction operator; second,
it can  be  used  for spatial  modeling  in collision  detection  and
trajectory planning for manipulators  and vehicles; and third, it can
be used  to  localize an  object  in 3-D  space  from a  sequence  of
silhouette views. The  intersection algorithm consists of  two parts:
first, there is a geometric part in which all the faces and edges are
compared with each other for potential face/edge intersections called
piercing points; and second, there is  a topological part in which the
results  are  "copied off"  of  the  given polyhedra;  the  results may
consist of zero, one or many polyhedra. In the following, the "operands"
refers to the sets of polyhedra given to BIN as arguments and the "result"
refers to the set (possibly empty) of polyhedra produced by BIN.{Q}

{I660,0;FCJC} FIGURE 5.1  -  POLYHEDRON  INTERSECTION,  UNION  AND  SUBTRACTION.{
H3;X0.61;I300,630;*BIN1.PLT;
I565,0;JC;FA} TWO OPERANDS: STAR AND CYLN{
I650,1;⊗BIN2.PLT;I∂0,∂630;⊗BIN3.PLT; I∂580,120;
}INTERSECTION: BIN(STAR,CYLN){I∂0,650;
}UNION: EVERT(BIN(EVERT(STAR),EVERT(CYLN))){
I1250,1;⊗BIN4.PLT;I∂0,∂630;⊗BIN5.PLT;I∂580,70;
}SUBTRACTION: BIN(EVERT(STAR),CYLN){I∂0,690;
}SUBTRACTION: BIN(STAR,EVERT(CYLN)){JUFAQ}
⊂5.1	Intersection Geometry.⊃

	The geometric part of the  polyhedron intersection algorithm,
BIN,   conceptually consists of  comparing each face  of one argument
with every edge of  the other argument and  vice versa.  In  practice
the  potentially N-squared  compares are  avoided by  using the  same
recursive  window partition  sort that  was used  in the  hidden line
eliminator, OCCULT (subsection 4.3). Ignoring the recursive windowing
for a  moment,  the inner  most face-edge compare of  BIN consists of
four steps: opposition,  intersection,  enclosure and fission.

	<Opposition Test>.  Given a face F and  an edge E, first, the
endpoints of  the edge are checked to see  whether they are in opposite
halfspaces with respect to the plane of the face. In terms  of vector
geometry, the dot  product of the face vector and  each vertex vector
is  taken and the  signs compared; different signs  indicate that the
vertices are in different  halfspaces.  The opposition  test requires
six  multiplications. <Intersection  Locus>. The  locus of  the point
where the edge pierces the plane of the face is computed.  <Enclosure
Test>.  Next the edge  is tested to see if it actually passes thru the
interior of the  face. In BIN,  this test exploits the face convexity
restriction.   The test consists  of crossing  neighboring pairs  of
vectors radiating from  the face plane piercing point  to each vertex
of  the given face and testing for a  sign change.  In practice, only
one component of the cross product needs be evaluated and so only two
multiplications per edge of the face are required. <Edge Fission>. If
the edge pierces the face, then  the edge is split (using the  ESPLIT
and BLED  routines) forming  a new  vertex,   called a face  piercing
vertex. A  temporary link of the vertex (left half  of word 7) is set
to point at the  face that was  pierced and the PED  link of the  new
vertex is set  to point at the  one of its two edges that  is external to
the surface.

FIGURE 5.2  -  FACE  PIERCING  GEOMETRY.
{Q}
⊂5.2	Intersection Topology.⊃

	After all the face piercing vertices have been made (assuming
no  pathological cases, see section  5.3), the edges  and vertices of
the result can be created in relation to  the faces,
edges,   and vertices of the  given polyhdera.
However in order to explain the details of the
relationship three definitions are needed:
"interior", "surface" and "surface loop".
In figure 5.3, two solid hexahedrons are being intersected,
on the left the surface loop of the intersection is
intensified (heavy lined) on the right the interior edges are intensified.

{FCJC} FIGURE 5.3  -  SURFACE EDGES AND INTERIOR EDGES OF RESULT. {JUFA}


In  particular,  each
piercing  vertex  has a  corresponding  vertex which  is  a trihedral
corner  of   the   result.
The correspondence is maintained in a temporary link field named
ALT; the alternate vertices and edges  that belong to the result  are
created by two topological trace routines:  the MKSURF routine, which
makes surface  edges and vertices of the  result starting its surface
loop trace  when given "un-ALT'ered"  face piercing  vertex; and  the
ETRACE routine, which makes edges and vertices interior to the result
polyhedron by  tracing the edge graph bounded by pierce vertices. The
new result edges are temporarily linked to the old operand faces. The
MKSURF  and ETRACE routines  are followed  by three steps  that fixup
surface wings, interior wings and face nodes so that a legally formed
result polyhedron is completed.

{FCJC} FIGURE 5.4  -  FETCH OTHER PIERCE-VERTEX OF A FACE. {JUFA}

	Fixup  step-1 places  vertex  and wing  pointers  in all  the
non-surface  edges.  A  non-surface  edge  is  distinguished  by  its
non-zero ALT link, and the new  vertices are provided with an A as  a
first edge,  PED, if it be lacking.
{λ10;JAF3}	A←BODY0;
WHILE (A←PED(A)) ≠ BODY0 DO IF (E←ALT(A))≠0 THEN
BEGIN
	PVT(A)	←V←	ALT(PVT(E)); IF PED(V)=0 THEN PED(V)←A;
	NVT(A)	←V←	ALT(NVT(E)); IF PED(V)=0 THEN PED(V)←A;
	NCW(A)	←	ALT(NCW(E));
	PCW(A)	←	ALT(PCW(E));
	NCCW(A)	←	ALT(NCCW(E));
	PCCW(A)	←	ALT(PCCW(E));
END;
{λ30;JUFA}
	Fixup  step-2 wings  together  the surface  vertex  tridedral
corners.  Since by  good luck  all  surface vertices  are necessarily
trihedral, the edges can be passed to the WING primitive for oriented
linking, in  any order.   The two surface  wings of a  surface vertex
were  stored in the NED and PED links  by MKSURF; the inward wing can
be retrieve as the PED(ALT(U)). Surface vertices are distinguished by
their ALT vertex having his SURBIT on.;

	Fixup step-3 replaces the alein faces of the result body with
native faces; this  is done  by scaning the  edge ring  of the  body,
testing the  two faces  of each  edge to  see if they  belong to  the
result body,   and if a  face doesn't belong it is  replaced by a new
one.  Face replacement,  as ususal,  requires clocking around  a face
perimeter and changing the appropriate face link in each edge.

⊂5.3	Special Cases.⊃

	In order of  difficulty from easy  to hard, the  four special
cases  that must  be handled are  non-intersection,   extremely short
edges, face  holes  and  coincident  entities.  ~<Non-Intersection>~.
When the face-edge compare (by  recursive window spacee sort) returns
no  piercing  points,   it  implies that  the surfaces  of  the given
polyhedra do  not intersect  and that  a  further test  is needed  to
determine whether the operands  are disjoint (and so the intersection
be empty) or whether  one operand contains  the other. ~<Face  Holes>~.
Because EVERT'ed solids are  allowed,  one polyhedron can  cut a hole
in a face of  the other without intersecting any of the edges of that
face, which would fool the copy-trace.   So as a preliminary step  to
BIN, all  the surface loops  are traced  and checked to  make certain
they cross  more than one face.  If a one face surface-loop is found,
the face  is  pyramided to  a vertex  interior  to the  surface-loop.
~<Short  Edges>~. An application  of BIN  can create edges  with almost
zero length,  which  require  an  extra  pass  to  find  and  delete.
~<Coincidant  Entities>~. Even  though an  occassional  edge that  lies
exactly  in  the plane  of  a face  can  be fudged  off  in  a random
direction and the  resulting extremely short  edges supressed; it  is
meaningful to try  to intersect two polyhedra which  have many faces,
edges and vertices that are exactly coincident - which usually causes
the present implementation to fail.

{FCJC} FIGURE 5.5 - EXAMPLE OF FACE HOLE FIXUP. {JUFA}

⊂5.4	Face Convexity Coercion.⊃

	Since, both the body intersection method, BIN, and the hidden
line eliminator, OCCULT,  are restricted to convex face polyhdera; it
is essential to have a method that detects and subdivides the concave
faces of a given polyhedron. The routine MKCNVX, make convex, reduces
the  concave faces of a body into  reasonible convex faces. The whole
method consists of  two steps:  first, the face  is broken down  into
triangles and second, the  longest unnecessary new edges are removed.
The atomization to triangles step is recursive: the pointiest extrema
vertex, V0, is  lopped off, if no other  vertices of the face  are on
the same side  of the line segment between V0's immediate neighboring
vertices: OTHER(ECCW(V0,F),V0) and  OTHER(ECW(V0,F),V0).  An  extrema
vertex is one that touchs  the smallest circumscribed rectangle whoes
sides  are parellel to  the coordinate axes; the  pointiest vertex is
the one with  the largest cosine.   This make-convex method is  craft
that was  evolved without benefit  of theory. The  performance of the
method is startlingly  good, it automatically  convexes polygons  the
same way that I would.

{FCJC} FIGURE 5.6  -  EXAMPLES OF FACE CONVEXITY COERCION. {JUFA}

⊂5.5	Body Cutting.⊃

	Body  cutting  is  the operation  of  dividing  an  arbitrary
polyhedron into sets  of parts above and below a given cutting plane.
Although cutting is simply a special case of polyhedron intersection,
the  process  is sufficiently  important  and  different to  merit  a
separate implementation.

{FCJC} FIGURE 5.7  -  BODY CUTTING ILLUSTRATED. {JUFA}
⊂5.6	Performance and Related Work.⊃